package com.algoruthm6;

import java.util.Arrays;

public class MergeSort {

    public static int[] sort(int[] array){
        if(array.length<2)
            return array;
        int mid = (0+array.length)/2;
        int[] left = Arrays.copyOfRange(array,0,mid);
        int[] right = Arrays.copyOfRange(array,mid,array.length);
        return merge(sort(left),sort(right));
    }

    public static int[] merge(int[] left,int[] right){
        int i=0,j=0;
        int p=left.length,q=right.length;
        int[] temp = new int[p+q];
        int s = 0;
        while(i<p&&j<q){
            if(left[i]<right[j]){
                temp[s++] = left[i++];
            }else{
                temp[s++] = right[j++];
            }
        }
        if(i==p){
            while(j<q){
                temp[s++] = right[j++];
            }
        }else{
            while(i<p){
                temp[s++] = left[i++];
            }
        }
        return temp;
    }

    public static void main(String[] args){
        int[] array = new int[]{4,3,6,8,9,7,10,5,1,2};
        System.out.println("array:"+ Arrays.toString(array));
        int[] result=sort(array);
        System.out.println("sorted array:"+ Arrays.toString(result));
    }

}
